{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈 的构造"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack(object):\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        创建一个Stack类\n",
    "        对栈进行初始化参数设计\n",
    "        \"\"\"\n",
    "        self.stack = []  # 存放元素的栈\n",
    "\n",
    "    def push(self, data):\n",
    "        \"\"\"\n",
    "        压入 push ：将新元素放在栈顶\n",
    "        当新元素入栈时，栈顶上移，新元素放在栈顶。\n",
    "        \"\"\"\n",
    "        self.stack.append(data)\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"\n",
    "        弹出 pop ：从栈顶移出一个数据\n",
    "        - 栈顶元素拷贝出来\n",
    "        - 栈顶下移\n",
    "        - 拷贝出来的栈顶作为函数返回值\n",
    "        \"\"\"\n",
    "        # 判断是否为空栈\n",
    "        if self.stack:\n",
    "            return self.stack.pop()\n",
    "        else:\n",
    "            raise IndexError(\"从空栈执行弹栈操作\")\n",
    "\n",
    "    def peek(self):\n",
    "        \"\"\"\n",
    "        查看栈顶的元素\n",
    "        \"\"\"\n",
    "        # 判断栈是否为空\n",
    "        if self.stack:\n",
    "            return self.stack[-1]\n",
    "\n",
    "    def is_empty(self):\n",
    "        \"\"\"\n",
    "        判断栈是否为空\n",
    "        \"\"\"\n",
    "        # 栈为非空时，self.stack为True，再取反，为False\n",
    "        return not bool(self.stack)\n",
    "\n",
    "    def size(self):\n",
    "        \"\"\"\n",
    "        返回栈的大小\n",
    "        \"\"\"\n",
    "        return len(self.stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_number(aString):\n",
    "    \"\"\"\n",
    "    判断一个字符串是否是一个数字或者浮点数\n",
    "    是，返回True\n",
    "    否，返回False\n",
    "    \"\"\"\n",
    "    try:\n",
    "        float(aString)\n",
    "        return True\n",
    "    except:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Strng2ListofString(aString):\n",
    "    \"\"\"\n",
    "    将一个中缀表达式拆分\n",
    "    数字（包括整数和浮点数）、符号 拆分成单个字符\n",
    "    \"\"\"\n",
    "    symbol_list = ['+', '-', '*', '/', '(', ')']\n",
    "\n",
    "    # 补全前后符号，便于后续操作\n",
    "    aString = aString + '+'\n",
    "\n",
    "    # 存放拆分后的字符\n",
    "    char_list = []\n",
    "    single_char = \"\"\n",
    "\n",
    "    for char in aString:\n",
    "        # 如果char不在指定的符号集中，则认为是数字\n",
    "        if char not in symbol_list:\n",
    "            single_char += char\n",
    "        else:\n",
    "            char_list.append(single_char)\n",
    "            char_list.append(char)\n",
    "            single_char = \"\"\n",
    "    # 删掉\n",
    "    char_list = [char for char in char_list if char != '']\n",
    "    char_list = char_list[:-1]\n",
    "\n",
    "    return char_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def infix2postfix(strings):\n",
    "    \"\"\"\n",
    "    输入：未经处理的原始中缀表达式\n",
    "    输出：后缀表达式（拆成单个字符组成列表）\n",
    "    \"\"\"\n",
    "\n",
    "    # 给定符号的优先级次序，后续压栈，弹栈规则使用\n",
    "    priority_dict = {\n",
    "        '(': 0,\n",
    "        '+': 10,\n",
    "        '-': 10,\n",
    "        '*': 20,\n",
    "        '/': 20,\n",
    "        ')': 30, }\n",
    "\n",
    "    # 将数据字符串表达式处理为 单字符列表\n",
    "    strings = Strng2ListofString(strings)\n",
    "    \n",
    "    \n",
    "    # 为了兼顾输入表达式，头一个符号为0的情况\n",
    "    # 对于-2*3这种，改写成 0-2*3 的形式\n",
    "    if strings[0] == '-':\n",
    "        strings.insert(0, '0')\n",
    "\n",
    "    # 首先创建空的 栈 数据结构，为后续做好准备\n",
    "    stack = Stack()\n",
    "\n",
    "    # 创建空的列表，存放后缀表达式\n",
    "    postfix = []\n",
    "\n",
    "    for char in strings:\n",
    "\n",
    "        # 先判断当前字符是否为数字，若是，该方法返回True，直接附加到后缀表达式中去\n",
    "        if is_number(char):\n",
    "            postfix.append(char)\n",
    "\n",
    "        # 若不是数字，再进行其他分析\n",
    "        # 若是左括号，直接压栈\n",
    "        elif char == \"(\":\n",
    "            stack.push(char)\n",
    "\n",
    "        # 若是右括号，则依次弹栈，直到遇到左括号\n",
    "        elif char == \")\":\n",
    "            while stack.peek() != \"(\":\n",
    "                postfix.append(stack.pop())\n",
    "\n",
    "            # 将符号弹出到后缀表达式后，再将（ 弹栈，注意，只弹栈，不输出到后缀表达式\n",
    "            stack.pop()\n",
    "\n",
    "        # 如果是加减乘除\n",
    "        elif (char == '+' or char == '-' or char == '*' or char == '/'):\n",
    "            # 如果当前符号的优先级小于等于栈顶元素，且栈为非空，则弹栈\n",
    "            if (stack.is_empty() != True) and (priority_dict[char] <= priority_dict[stack.peek()]):\n",
    "                while (stack.is_empty() != True) and (priority_dict[char] <= priority_dict[stack.peek()]):\n",
    "                    postfix.append(stack.pop())\n",
    "                # 一直弹栈到满足压栈的要求为止，则将当前字符压栈\n",
    "                stack.push(char)\n",
    "            # 如果当前字符本身优先级就比栈顶元素优先级高，或者当前为空栈，则直接执行压栈操作\n",
    "            else:\n",
    "                stack.push(char)\n",
    "\n",
    "    # 如果在遍历完表达式后栈不为空，则依次弹栈\n",
    "    while stack.is_empty() != True:\n",
    "        postfix.append(stack.pop())\n",
    "\n",
    "    return postfix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_postfix(postfix_list):\n",
    "    \"\"\"\n",
    "    输入后缀表达式\n",
    "    输出计算结果\n",
    "    \"\"\"\n",
    "    stack = Stack()\n",
    "\n",
    "    for char in postfix_list:\n",
    "        if is_number(char):\n",
    "            stack.push(char)\n",
    "        elif char == '+':\n",
    "            top_num = float(stack.pop())\n",
    "            sec_num = float(stack.pop())\n",
    "            res = sec_num + top_num\n",
    "            stack.push(res)\n",
    "        elif char == '-':\n",
    "            top_num = float(stack.pop())\n",
    "            sec_num = float(stack.pop())\n",
    "            res = sec_num - top_num\n",
    "            stack.push(res)\n",
    "        elif char == '*':\n",
    "            top_num = float(stack.pop())\n",
    "            sec_num = float(stack.pop())\n",
    "            res = sec_num * top_num\n",
    "            stack.push(res)\n",
    "        elif char == '/':\n",
    "            top_num = float(stack.pop())\n",
    "            sec_num = float(stack.pop())\n",
    "            res = sec_num / top_num\n",
    "            stack.push(res)\n",
    "\n",
    "    res = stack.pop()\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cal_infix(aString):\n",
    "    \"\"\"\n",
    "    输入：原始的中缀表达式，\n",
    "    输出：表达式的计算结果\n",
    "    \n",
    "    中间步骤：\n",
    "        1.将原始中缀表达式转写为后缀表达式（包含了首位为负号‘-’的处理）infix2postfix\n",
    "        2.计算后缀表达式 cal_postfix\n",
    "    \"\"\"\n",
    "    return cal_postfix(infix2postfix(aString))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20.2\n",
      "1.8000000000000007\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    print(cal_infix(\"9.2+(3-1)*3+10/2\"))\n",
    "    print(cal_infix(\"-9.2+(3-1)*3+10/2\"))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
